/*
 * @Author: szx
 * @Date: 2021-11-29 13:19:51
 * @LastEditTime: 2021-11-29 14:12:56
 * @Description:
 * @FilePath: \leetcode\700-799\786\786.js
 */

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
// var kthSmallestPrimeFraction = function (arr, k) {
//     const n = arr.length;
//     const frac = [];
//     for (let i = 0; i < n; ++i) {
//         for (let j = i + 1; j < n; ++j) {
//             frac.push([arr[i], arr[j]]);
//         }
//     }
//     frac.sort((x, y) => x[0] * y[1] - y[0] * x[1]);
//     return frac[k - 1];
// };

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var kthSmallestPrimeFraction = function (arr, k) {
    const len = arr.length;
    const queue = new PriorityQueue({
        compare: (e1, e2) => {
            return e2[0] / e2[1] - e1[0] / e1[1];
        }
    });
    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j < len; j++) {
            if (queue.size() < k) {
                queue.enqueue([arr[i], arr[j]]);
            } else {
                const [x, y] = queue.front();
                if (x / y > arr[i] / arr[j]) {
                    queue.dequeue();
                    queue.enqueue([arr[i], arr[j]]);
                }
            }
        }
    }
    return queue.front();
};

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */

kthSmallestPrimeFraction([1, 2, 3, 5], 3);
class PriorityQueue {
    constructor(maxSize) {
        //设置默认的最大大小（如果未提供）
        if (isNaN(maxSize)) {
            maxSize = 10;
        }
        this.maxSize = maxSize;
        //初始化一个包含队列值的数组。
        this.container = [];
    }
    //帮助程序功能在开发时显示所有值
    display() {
        console.log(this.container);
    }
    //检查队列是否为空
    isEmpty() {
        return this.container.length === 0;
    }
    //检查队列是否已满
    isFull() {
        return this.container.length >= this.maxSize;
    }
    enqueue(data, priority) {
        //检查队列是否已满
        if (this.isFull()) {
            console.log('队列溢出！');
            return;
        }
        let currElem = new this.Element(data, priority);
        let addedFlag = false;
        //由于我们要添加元素以结束，因此我们将其推送。
        for (let i = 0; i < this.container.length; i++) {
            if (currElem.priority < this.container[i].priority) {
                this.container.splice(i, 0, currElem);
                addedFlag = true;
                break;
            }
        }
        if (!addedFlag) {
            this.container.push(currElem);
        }
    }
    dequeue() {
        //检查是否为空
        if (this.isEmpty()) {
            console.log('队列下溢！');
            return;
        }
        return this.container.pop();
    }
    peek() {
        if (isEmpty()) {
            console.log('队列下溢！');
            return;
        }
        return this.container[this.container.length - 1];
    }
    clear() {
        this.container = [];
    }
}
//创建一个内部类，用于在队列中创建新节点
//每个元素都有一些数据和优先级
PriorityQueue.prototype.Element = class {
    constructor(data, priority) {
        this.data = data;
        this.priority = priority;
    }
};
